1. Field of the Invention
The present invention relates to method and apparatus for checking read errors using two CRC (Cyclic Redundancy Check) stages, and preferably to method and apparatus for detecting errors read from a magnetic disk storage medium in the read channel of a hard disk drive. The present invention also relates to method and apparatus for detecting and correcting such errors.
2. Background Information
In a data storage system (such as a computer hard disk drive), it is very important that the data read from the data storage system is accurate. One solution is to use an error-correcting code (ECC, such as Reed-Solomon code, etc.) to correct the errors in the data read out from the storage device. However, if the number of errors in the read out data is greater than the designed ECC correction power, there is a small probability that the ECC unit may add errors to the data; this is called miscorrection. A second error detection code, usually a cyclic redundancy check (CRC) code, may be used to detect such miscorrection. Each of U.S. Pat. Nos. 5,157,669; 5,671,237, and 5,909,334 describes circuitry and processes for detecting and correcting errors in digital data read from disk storage media. The contents of these three U.S. patents is incorporated herein by reference.
A disk drive data sector typically has 512 bytes of data, denoted B0, B1, . . . , B511. CRC bytes are calculated using all 512 bytes of data. In the following description, 4 CRC bytes will be used for simplicity. However, the techniques described can be easily used with other numbers of CRC bits/bytes, as needed. The techniques described below can be easily modified for other numbers of CRC bytes or other sector sizes.
Let C0, C1, C2, C3 be the 4 CRC bytes. Each byte includes 8 bits. Bits bi,0, . . . , bi,7 denote the 8 bits of the byte Bi, and a similar notation is used for other bytes. Let:
                              g          ⁡                      (            x            )                          =                              ∑                          i              =              0                        32                    ⁢                                          ⁢                                    g              i                        ⁢                          x              i                                                          (        1        )            be the generator polynomial of the CRC code, where gi is either 0 or 1.
Now, let NI be the number of interleaves and Ui be XOR sum of data bytes across the interleaves, that is:Ui=BN,xi+BNIxi+1 . . . +BNIxi+NI−1, and Bi=0 if i≧s  (2)where the “+” is a bitwise XOR operation, and s is the number of data bytes per sector. If other data (e.g., SPBA) needs to be protected by ECC and CRC, these data are treated as user data. (Example, U0=B0+B1+B2 in three interleave case, and U0=B0+B1+B2+B3 in four interleave case).
Let k be the least integer that greater than or equal to the number of data bytes divide by the number of interleaves, that is,k=┌s÷NI┐.  (3)
The CRC encoder calculates the remainder r(x) of the following polynomial:
                              x          L                ×                  (                                    ∑                              i                =                0                                            k                -                1                                      ⁢                                                  ⁢                                          ∑                                  j                  =                  0                                7                            ⁢                                                          ⁢                                                u                                                            (                                              k                        -                        1                        -                        i                                            )                                        ,                    j                                                  ·                                  x                                                            8                      ⁢                      i                                        +                    j                                                                                )                                    (        4        )            divided by the generator polynomial of the CRC code, where L is the number of CRC bits. The 32 coefficients of r(x) form the 4 CRC bytes: C0=(r24, . . . , r31), C1=(r16, . . . , r23), C2=(r8, . . . , r15), C3=(r0, . . . , r7). Note that the bits order of the four CRC bytes does not matter as long as the CRC encoding and CRC checking units agree on the CRC bits order.
In three interleave case, all data are arranged as follows:
FirstB0B3. . .B507B510C1D0,0D0,1. . .D0,2t−1interleaveSecondB1B4. . .B508B511C2D1,0D1,1. . .D1,2t−1interleaveThirdB2B5. . .B509C0C3D2,0D2,1. . .D2,2t−1interleavewhere Di,0, . . . , Di,2t−1 are the ECC bytes for the ith interleave generated by a Reed-Solomon encoder, and 2t is the number of ECC bytes per interleave.
In the four interleave case, the data arrangement would look like:
FirstB0B4. . .B508C0D0,0D0,1. . .D0,2t−1interleaveSecondB1B5. . .B509C1D1,0D1,1. . .D1,2t−1interleaveThirdB2B6. . .B510C2D2,0D2,1. . .D2,2t−1interleaveFourthB3B7. . .B511C3D3,0D3,1. . .D3,2t−1interleave
The three interleave case will be described in the following. All the data are written on the disk in the following “normal” order:                B0, B1, . . . , B511, C0, . . . , C3, Do0, D1,0, D2,0, . . . , D0,2t−1, D1,2t−1, D2,2t−1         
In FIG. 1, data to be written on a disk is supplied to a CRC encoder 12, then to an ECC encoder 14, for writing onto disk 18 with head 16. When data is read back from the disk 18 with head 22, the data is often corrupted with errors. After the data is stored in the buffer memory 50, the ECC unit 24 computes the error values and the error locations. The buffer manager 48 (BM) takes the error values and error locations, and corrects the errors in the memory 50. Because the CRC unit 26 does not have access to the data after ECC correction by the ECC unit 24, the CRC unit 26 does the CRC check using the error vector and the data before ECC correction.
Another problem is that, the ECC unit 24 generates the error vector in a different order.
Instead of generating the error vector in the normal order shown below:                EB0, EB1, . . . , EB511, EC0, EC1, EC2, EC3, ED0,0, . . . , ED2,2t−1,the ECC unit 24 generates the errors in a “reversed interleaved order”, shown below:        ED0,2t−1, ED0,2t−2, . . . , ED0,0, EC1, EB510, EB507, . . . , EB0 then        ED1,2t−1, ED1,2t−2, . . . , ED1,0, EC2, EB511, EB508, . . . , EB1 and then        ED2,2t−1, ED2,2t−2, . . . , ED2,0, EC3, EC0, EB509, EB506, . . . , EB2 where the notation EB0 means the error value at the position of B0, that is, data read back is actually RB0=(B0+EB0). Note that most entries in the error sequence are zeros.        
Thus, what is needed is a error detection technique which reliably and accurately detects errors in read digital data.